SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Truncated binary encoding</title>

</head>

Truncated binary encoding

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Truncated binary encoding is an <a href="Entropy_encoding" class="mw-redirect" title="Entropy encoding">entropy encoding</a> typically used for uniform <a href="Probability_distribution" title="Probability distribution">probability distributions</a> with a finite alphabet. It is parameterized by an alphabet with total size of number n. It is a slightly more general form of <a href="Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary encoding</a> when n is not a <a href="Power_of_two" title="Power of two">power of two</a>.

If n is a power of two, then the coded value for 0 ≤ x < n is the simple binary code for x of length log2(n). Otherwise let k = floor(log2(n)), such that 2k < n < 2k+1and let u = 2k+1 − n.

Truncated binary encoding assigns the first u symbols codewords of length k and then assigns the remaining n − u symbols the last n − u codewords of length k + 1. Because all the codewords of length k + 1 consist of an unassigned codeword of length k with a "0" or "1" appended, the resulting code is a <a href="Prefix_code" title="Prefix code">prefix code</a>.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Used since at least 1984, phase-in codes, also known as economy codes,<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> are also known as truncated binary encoding.

<div class="mw-heading mw-heading2"><h2 id="Example_with_n_=_5">Example with n = 5</h2></div>

For example, for the alphabet {0, 1, 2, 3, 4}, n = 5 and 22 ≤ n < 23, hence k = 2 and u = 23 − 5 = 3. Truncated binary encoding assigns the first u symbols the codewords 00, 01, and 10, all of length 2, then assigns the last n − u symbols the codewords 110 and 111, the last two codewords of length 3.

For example, if n is 5, plain binary encoding and truncated binary encoding allocates the following <a href="Code_word_(communication)" title="Code word (communication)">codewords</a>. Digits shown <del>struck</del> are not transmitted in truncated binary.

<th>Truncated binary</th>

<th colspan="3">Encoding</th>

<th>Standard binary

</th></tr>

<tr>

<td align="left">0

</td></tr>

<tr>

<td align="left">1

</td></tr>

<tr>

<td align="left">2

</td></tr>

<tr>

<td align="right">UNUSED</td>

<td align="left">3

</td></tr>

<tr>

<td align="right">UNUSED</td>

<td align="left">4

</td></tr>

<tr>

<td align="right">UNUSED</td>

<td align="left">5/UNUSED

</td></tr>

<tr>

<td align="left">6/UNUSED

</td></tr>

<tr>

<td align="left">7/UNUSED

</td></tr></tbody></table>

It takes 3 bits to encode n using straightforward binary encoding, hence 23 − n = 8 − 5 = 3 are unused.

In numerical terms, to send a value x, where 0 ≤ x < n, and where there are 2k ≤ n < 2k+1 symbols, there are u = 2k+1 − n unused entries when the alphabet size is rounded up to the nearest power of two. The process to encode the number x in truncated binary is: if x is less than u, encode it in k binary bits; if x is greater than or equal to u, encode the value x + u in k + 1 binary bits.

<div class="mw-heading mw-heading2"><h2 id="Example_with_n_=_10">Example with n = 10</h2></div>

Another example, encoding an alphabet of size 10 (between 0 and 9) requires 4 bits, but there are 24 − 10 = 6 unused codes, so input values less than 6 have the first bit discarded, while input values greater than or equal to 6 are offset by 6 to the end of the binary space. (Unused patterns are not shown in this table.)

<th>Input value</th>

<th>Offset</th>

<th>Offset value</th>

<th>Standard binary</th>

<th>Truncated binary

</th></tr>

<tr>

<td>000

</td></tr>

<tr>

<td>001

</td></tr>

<tr>

<td>010

</td></tr>

<tr>

<td>011

</td></tr>

<tr>

<td>100

</td></tr>

<tr>

<td>101

</td></tr>

<tr>

</td></tr>

<tr>

<td>1100

</td></tr>

<tr>

<td>1101

</td></tr>

<tr>

<td>1110

</td></tr>

<tr>

<td>1111

</td></tr></tbody></table>

To decode, read the first k bits. If they encode a value less than u, decoding is complete. Otherwise, read an additional bit and subtract u from the result.

<div class="mw-heading mw-heading2"><h2 id="Example_with_n_=_7">Example with n = 7</h2></div>

Here is a more extreme case: with n = 7 the next power of 2 is 8, so k = 2 and u = 23 − 7 = 1:

<th>Input value</th>

<th>Offset</th>

<th>Offset value</th>

<th>Standard binary</th>

<th>Truncated binary

</th></tr>

<tr>

<td>00

</td></tr>

<tr>

</td></tr>

<tr>

<td>010

</td></tr>

<tr>

<td>011

</td></tr>

<tr>

<td>100

</td></tr>

<tr>

<td>101

</td></tr>

<tr>

<td>110

</td></tr>

<tr>

<td>111

</td></tr></tbody></table>

This last example demonstrates that a leading zero bit does not always indicate a short code; if u < 2k, some long codes will begin with a zero bit.

<div class="mw-heading mw-heading2"><h2 id="Simple_algorithm">Simple algorithm</h2></div>

Generate the truncated binary encoding for a value x, 0 ≤ x < n, where n > 0 is the size of the alphabet containing x. n need not be a power of two.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>string TruncatedBinary (int x, int n)

{

// Set k = floor(log2(n)), i.e., k such that 2^k <= n < 2^(k+1).

int k = 0, t = n;

while (t > 1) { k++; t >>= 1; }

// Set u to the number of unused codewords = 2^(k+1) - n.

int u = (1 << k + 1) - n;

if (x < u)

return Binary(x, k);

else

return Binary(x + u, k + 1));

}

</pre></div>

The routine <code>Binary</code> is expository; usually just the rightmost <code>len</code> bits of the variable x are desired.

Here we simply output the binary code for x using <code>len</code> bits, padding with high-order 0s if necessary.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>string Binary (int x, int len)

{

string s = "";

while (x != 0) {

if (even(x))

s = '0' + s;

else s = '1' + s;

x >>= 1;

}

while (s.Length < len)

s = '0' + s;

return s;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="On_efficiency">On efficiency</h2></div>

If n is not a power of two, and k-bit symbols are observed with probability p, then (k + 1)-bit symbols are observed with probability 1 − p. We can calculate the expected number of bits per symbol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{e}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{e}}</annotation>

</semantics>

</math><img src="./975a5d457db9b1ce726aba01dc15c502ca3b9d89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.996ex; height:2.509ex;" alt="{\displaystyle b_{e}}" loading="lazy"> as

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{e}=pk+(1-p)(k+1).}</annotation>

</semantics>

</math><img src="./59521d3383fe08c10db271e6e0258497539ffbff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.967ex; height:2.843ex;" alt="{\displaystyle b_{e}=pk+(1-p)(k+1).}" loading="lazy"></dd></dl>

Raw encoding of the symbol has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{u}=k+1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{u}=k+1}</annotation>

</semantics>

</math><img src="./db6196fe3d98b9abc2a060f96e65aefd0ace67ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.483ex; height:2.509ex;" alt="{\displaystyle b_{u}=k+1}" loading="lazy"> bits. Then relative space saving s (see <a href="Data_compression_ratio" title="Data compression ratio">Data compression ratio</a>) of the encoding can be defined as

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.}</annotation>

</semantics>

</math><img src="./883202942a2e2020c55c917daf2657a9d43c9a1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:39.008ex; height:6.176ex;" alt="{\displaystyle s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.}" loading="lazy"></dd></dl>

When simplified, this expression leads to

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.}</annotation>

</semantics>

</math><img src="./8febb04c62b729febd1d6c930ff01f9bd7b91151.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:16.991ex; height:5.343ex;" alt="{\displaystyle s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.}" loading="lazy"></dd></dl>

This indicates that relative efficiency of truncated binary encoding increases as probability p of k-bit symbols increases, and the raw-encoding symbol bit-length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{u}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{u}}</annotation>

</semantics>

</math><img src="./eaa5c6e69f02d1037f23ecaeb9d05a9e18ef2f24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.17ex; height:2.509ex;" alt="{\displaystyle b_{u}}" loading="lazy"> decreases.

<ul><li><a href="Benford's_law" title="Benford's law">Benford's law</a></li>

<li><a href="Golomb_coding" title="Golomb coding">Golomb coding</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Eastman, Willard L, et al. (Aug. 1984) <a rel="nofollow" class="external text" href="https://patentimages.storage.googleapis.com/86/7d/56/dd49314023387d/US4464650.pdf">Apparatus and Method for Compressing Data Signals and Restoring the Compressed Data Signals</a>, US Patent 4,464,650.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> Acharya, Tinku et Já Já, Joseph F. (oct. 1996), <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/0020025596000898">An on-line variable-length binary encoding of text</a>, Information Sciences, vol 94 no 1-4, p. 1-22.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Job van der Zwan. <a rel="nofollow" class="external text" href="https://observablehq.com/@jobleonard/phase-in-codes">"Phase-in Codes"</a>.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-24" href="https://en.wikipedia.org/wiki/?title=Truncated_binary_encoding&oldid=1282068246">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>